#include <stdio.h>
#include "mybintree.h"
/*建立一个二叉树*/
BINNODE *createbt(){
    BINNODE *q;//临时生成的新结点 
    BINNODE *s[30];//指针数组，存放二叉树中的所有结点，最多只能有30个结点 
    int j,i;
    datatype x;//结点的数据域的值 
    printf("建立二叉树，输入结点对应的编号和值，编号和值之间用逗号隔开，编号从1开始，值以'$'为结束\n");
    printf("编号,字母=");
    scanf("%d,%c",&i,&x);
    while(i!=0&&x!='$'){
        q=(BINNODE *)malloc(sizeof(BINNODE));/*建立新结点*/
        q->data=x;/*x放入数据域*/
        q->lchild=NULL;
        q->rchild=NULL;/*左右孩子都为空*/
        s[i]=q;/*q结点地址存入s指针数组中*/
        if(i!=1){/*i=1，对应的结点是根结点*/
            j=i/2;/*求双亲结点的编号j*/
            if(i%2==0){
                s[j]->lchild=q;/*q结点编号为偶数则挂在双亲结点j的左边*/
			}else{
                s[j]->rchild=q;/*q结点编号为偶数则挂在双亲结点j的右边*/
			}
		}
		printf("编号,字母=");
		scanf("%d,%c",&i,&x);
	}
	return s[1];//返回根结点地址
}
/*先序遍历二叉树，递归实现*/
void preorder(BINNODE *root){
    if(root!=NULL){
    	printf("%c",root->data);/*访问根结点*/
    	preorder(root->lchild);/*访问左子树*/
    	preorder(root->rchild);/*访问右子树*/
	}
}
/*中序遍历二叉树，递归实现*/
void inorder(BINNODE *root){
    if(root!=NULL){
    	inorder(root->lchild);/*访问左子树*/
		printf("%c",root->data);/*访问根结点*/
    	inorder(root->rchild);/*访问右子树*/
    }
}
/*后序遍历二叉树，递归实现*/
void postorder(BINNODE *root){
    if(root!=NULL){
    	postorder(root->lchild);/*访问左子树*/
    	postorder(root->rchild);/*访问右子树*/
    	printf("%c",root->data);/*访问根结点*/
    }
}

/*求叶子结点数*/
int numOfLeaf(BINNODE *root)
{
   int num1,num2;
	if(root==NULL){
		return 0;/*如果树为空，返回0*/
	}else if((root->lchild==NULL)&&(root->rchild==NULL)){
        return 1;/*如果左右孩子全为空，返回1*/
	}else{/*如果左右孩子不全为空*/
        num1=numOfLeaf(root->lchild);/*递归调用左子树，num1为左子树的叶子结点数目*/
        num2=numOfLeaf(root->rchild);/*递归调用右子树，num1为右子树的叶子结点数目*/
        return num1+num2;
	}
} 

int numOfOneChild(BINNODE *root)
{	
	int num1,num2;
    if((root==NULL)||(root->lchild==NULL)&&(root->rchild==NULL)){
		return 0;/*如果树根结点为空或为叶子结点，返回0*/
	}
	if((root->lchild!=NULL)&&(root->rchild!=NULL)){/*根结点的度为2*/
        num1=numOfOneChild(root->lchild);/*递归调用左子树，num1为左子树的度为1的结点数目*/
        num2=numOfOneChild(root->rchild);/*递归调用右子树，num1为右子树的度为1的结点数目*/
        return num1+num2;/*返回左子树和右子树度为1的结点数目之和*/
	}else{/*根结点的度为1*/
        num1=numOfOneChild(root->lchild);/*递归调用左子树，num1为左子树的度为1的结点数目*/
		num2=numOfOneChild(root->rchild);/*递归调用右子树，num1为右子树的度为1的结点数目*/
        return num1+num2+1;/*返回左子树和右子树度为1的结点数目之和再加上根节点*/
	}
}

int numOfTwoChild(BINNODE *root)
{
    int num1,num2;
    if((root==NULL)||(root->lchild==NULL)&&(root->rchild==NULL)){
		return 0;/*如果树根结点为空或为叶子结点，返回0*/
	}
	if((root->lchild!=NULL)&&(root->rchild!=NULL)){/*根结点的度为2*/
        num1=numOfTwoChild(root->lchild);/*递归调用左子树，num1为左子树的度为2的结点数目*/
		num2=numOfTwoChild(root->rchild);/*递归调用右子树，num1为右子树的度为2的结点数目*/
        return num1+num2+1;;/*返回左子树和右子树度为2的结点数目之和再加上根节点*/
	}else{/*根结点的度为1*/
        num1=numOfTwoChild(root->lchild);/*递归调用左子树，num1为左子树的度为2的结点数目*/
		num2=numOfTwoChild(root->rchild);/*递归调用右子树，num1为右子树的度为2的结点数目*/
        return num1+num2;;/*返回左子树和右子树度为2的结点数目之和*/
	}

}
